package LeetCode.tree;

import java.util.Deque;
import java.util.LinkedList;

public class NC_194 {
    public boolean getPath(TreeNode root, TreeNode p, Deque<TreeNode> stack){
        if(root == null || p == null){  // O(TreeHigh)
            return false;
        }
        stack.push(root);
        if(p == root){
            return true;
        }
        boolean leftTree = getPath(root.left, p, stack);
        if(leftTree){
            return true;
        }
        boolean rightTree = getPath(root.right, p, stack);
        if(rightTree){
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q){
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(root,p,stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,q,stack2);
        int differ = stack1.size()-stack2.size();
        if(differ < 0){  // 让长度大的先走长度差步，使得两个长度一样
            while (differ != 0){
                stack2.pop();
                differ++;
            }
        }else {
            while (differ != 0){
                stack1.pop();
                differ--;
            }
        }
        while (!(stack1.isEmpty() && stack2.isEmpty())){
            TreeNode pop1 = stack1.pop();  // 同时移动 直到栈顶值一样
            TreeNode pop2 = stack2.pop();
            if(pop1 == pop2){
                return pop1;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        NC_194 n = new NC_194();
        TreeNode root = NC.main1();
        TreeNode p = root.left.left;
        TreeNode q = root.left.right;
        TreeNode res = n.lowestCommonAncestor2(root,p,q);
        System.out.println("\n" + res.val);
    }
}
